# -*- coding:utf-8 -*-
import heapq
import math
class Solution:
    # def __init__(self):
    #     self.num =[]
    # def Insert(self, num):
    #     # write code here
    #     heapq.heappush(self.num,num)
    # def GetMedian(self,n=0.0):
    #     # write code here
    #     mid =math.ceil(len(self.num)/2)
    #     return (heapq.nlargest(mid, self.num)[-1] + heapq.nsmallest(mid, self.num)[-1])/2.0

    minHeap = []
    maxHeap = []

    def Insert(self, num):
        if self.maxHeap and num > self.maxHeap[0]:
            heapq.heappush(self.maxHeap, num)
        else:
            heapq.heappush(self.minHeap, -num)
        if len(self.minHeap) - len(self.maxHeap) == 2:
            e = heapq.heappop(self.minHeap)
            heapq.heappush(self.maxHeap, -e)
        elif len(self.maxHeap) - len(self.minHeap) == 2:
            e = heapq.heappop(self.maxHeap)
            heapq.heappush(self.minHeap, -e)

    def GetMedian(self, _):
        if len(self.minHeap) - len(self.maxHeap) == 1:
            return -self.minHeap[0]
        if len(self.maxHeap) - len(self.minHeap) == 1:
            return self.maxHeap[0]
        else:
            return (-self.minHeap[0] + self.maxHeap[0]) / 2.


s =Solution()
d = [5,2,3,4,1,6,7,0,8]
for i in d:
    s.Insert(i)
    print(s.GetMedian(1))